import java.util.*;

/**
 * 133. 克隆图
 * https://leetcode-cn.com/problems/clone-graph/
 */
public class Solutions_133 {
    public static void main(String[] args) {
        /**
         * 构建无向图，共 4 个节点
         *   1 ------ 2
         *   |        |
         *   |        |
         *   |        |
         *   4 ------ 3
         */
        Node_133 node1 = new Node_133(1);
        Node_133 node2 = new Node_133(2);
        Node_133 node3 = new Node_133(3);
        Node_133 node4 = new Node_133(4);

        node1.neighbors = new ArrayList<>();
        node1.neighbors.add(node2);
        node1.neighbors.add(node4);

        node2.neighbors = new ArrayList<>();
        node2.neighbors.add(node1);
        node2.neighbors.add(node3);

        node3.neighbors = new ArrayList<>();
        node3.neighbors.add(node2);
        node3.neighbors.add(node4);

        node4.neighbors = new ArrayList<>();
        node4.neighbors.add(node1);
        node4.neighbors.add(node3);

        Node_133 result = cloneGraph2(node1);
        System.out.println(result);
    }

    /**
     * 解法二：广度优先搜索-bfs（41ms）
     */
    public static Node_133 cloneGraph2(Node_133 node) {
        if (node == null) {
            return null;
        }
        Map<Node_133, Node_133> map = new HashMap<>();
        // 完成初始节点映射
        map.put(node, new Node_133(node.val, new ArrayList<>()));
        Queue<Node_133> queue = new LinkedList<>();
        queue.add(node);

        while (!queue.isEmpty()) {
            Node_133 cur = queue.poll();
            for (Node_133 neighbor : cur.neighbors) {
                if (!map.containsKey(neighbor)) {
                    // 拷贝邻居节点，同时映射到 map 中
                    map.put(neighbor, new Node_133(neighbor.val, new ArrayList<>()));
                    queue.add(neighbor);
                }
                // 邻居结点拷贝完成后，将拷贝邻居节点的克隆对象
                map.get(cur).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }

    /**
     * 解法一：深度优先搜索-dfs（32ms）
     */
    public static Node_133 cloneGraph(Node_133 node) {
        if (node == null) {
            return null;
        }
        Map<Node_133, Node_133> map = new HashMap<>();
        dfs(map, node);
        return map.get(node);
    }

    public static void dfs(Map<Node_133, Node_133> map, Node_133 node) {
        if (map.containsKey(node)) {
            // 结束条件：已经记录到 map 中，那么其 neighbors 也一定完成了克隆
            return;
        }
        // 拷贝节点值，映射到 map 中
        map.put(node, new Node_133(node.val));
        List<Node_133> neighbors = node.neighbors;
        // 递归拷贝邻居节点
        for (Node_133 neighbor : neighbors) {
            // 递归，将 neighbor 都记录到 map 中
            dfs(map, neighbor);
            // 递归完成，邻居节点的拷贝都映射到了 map 中，所以直接从 map 中取
            map.get(node).neighbors.add(map.get(neighbor));
        }
    }
}

class Node_133 {
    public int val;
    // 邻居节点，可能有零个或多个，用列表记录
    public List<Node_133> neighbors;

    public Node_133() {
        val = 0;
        neighbors = new ArrayList<Node_133>();
    }

    public Node_133(int _val) {
        val = _val;
        neighbors = new ArrayList<Node_133>();
    }

    public Node_133(int _val, ArrayList<Node_133> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}